package 剑指II;

import 我的JDK基础数据结构.HashMap.HashMap;

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;
import java.util.Map;

/**
 * @description:
 * @author: 小白白
 * @create: 2021-12-15
 **/

public class Jz034外星语言是否排序 {

    /**
     * 某种外星语也使用英文小写字母，但可能顺序 order 不同。字母表的顺序（order）是一些小写字母的排列。
     * 给定一组用外星语书写的单词 words，以及其字母表的顺序 order，
     * 只有当给定的单词在这种外星语中按字典序排列时，返回 true；否则，返回 false。
     * <p>
     * 示例 1：
     * 输入：words = ["hello","leetcode"], order = "hlabcdefgijkmnopqrstuvwxyz"
     * 输出：true
     * 解释：在该语言的字母表中，'h' 位于 'l' 之前，所以单词序列是按字典序排列的。
     * 示例 2：
     * 输入：words = ["word","world","row"], order = "worldabcefghijkmnpqstuvxyz"
     * 输出：false
     * 解释：在该语言的字母表中，'d' 位于 'l' 之后，那么 words[0] > words[1]，因此单词序列不是按字典序排列的。
     * 示例 3：
     * 输入：words = ["apple","app"], order = "abcdefghijklmnopqrstuvwxyz"
     * 输出：false
     * 解释：当前三个字符 "app" 匹配时，第二个字符串相对短一些，然后根据词典编纂规则 "apple" > "app"，因为 'l' > '∅'，其中 '∅' 是空白字符，定义为比任何其他字符都小（更多信息）。
     *  
     * 提示：
     * 1 <= words.length <= 100
     * 1 <= words[i].length <= 20
     * order.length == 26
     * 在 words[i] 和 order 中的所有字符都是英文小写字母。
     */

    // 推荐的
    public boolean isAlienSorted(String[] words, String order) {

        // 只比对前后相邻的两个即可
        Map<Character, Integer> orderMap = new HashMap<>();
        char[] orderArr = order.toCharArray();
        for (int i = 0; i < orderArr.length; i++) {
            orderMap.put(orderArr[i], i);
        }

        for (int i = 0; i < words.length - 1; i++) {

            String word1 = words[i];
            String word2 = words[i + 1];

            int minLength = Math.min(word1.length(), word2.length());
            // 比较这两个
            for (int j = 0; j < minLength; j++) {
                if (word1.charAt(j) != word2.charAt(j)) {
                    if (orderMap.get(word1.charAt(j)) > orderMap.get(word2.charAt(j))) {
                        // 前面的大了
                        return false;
                    }
                    // 可以通过
                    break;
                }
            }

            // 通过的,末尾字符相等 && 前面长
            if (word1.charAt(minLength - 1) == word2.charAt(minLength - 1) && word1.length() > word2.length()) {
                return false;
            }

        }
        return true;
    }

    // 一般的
    public boolean isAlienSortedMid(String[] words, String order) {

        Map<Character, Integer> orderMap = new HashMap<>(order.length());
        char[] orderArr = order.toCharArray();

        for (int i = 0; i < orderArr.length; i++) {
            orderMap.put(orderArr[i], i);
        }

        // 看每一个字符是否排序的就可以了
        int index = 0;
        Deque<Integer> queue = new ArrayDeque<>();

        for (int i = 0; i < words.length; i++) {
            queue.addLast(i);
        }

        while (!queue.isEmpty()) {

            while (!queue.isEmpty() && index >= words[queue.peekFirst()].length()) {
                queue.removeFirst();
            }
            if (queue.isEmpty()) {
                return true;
            }
            Integer lastIndex = queue.removeFirst();
            Character lastC = words[lastIndex].charAt(index);
            int count = queue.size();

            while (count > 0) {
                // 相等的放入queue中
                Integer thisIndex = queue.removeFirst();
                // 后面的突然到尾巴,前面的还想和它(后面)的比,然而没得比了, abc ab => false
                if (words[thisIndex].length() == index) {
                    return false;
                }
                Character thisC = words[thisIndex].charAt(index);
                Integer lastOrder = orderMap.get(lastC);
                Integer thisOrder = orderMap.get(thisC);
                if (lastOrder > thisOrder) {
                    return false;
                }
                if (lastOrder.equals(thisOrder)) {
                    queue.addLast(lastIndex);
                    queue.addLast(thisIndex);
                }

                lastC = thisC;
                lastIndex = thisIndex;
                count--;
            }
            index++;
        }

        return true;
    }

    // 时间好慢的解法
    public boolean isAlienSortedLow(String[] words, String order) {

        Map<Character, Character> map = new HashMap<>(26);
        Map<String, Integer> indexMap = new HashMap<>(words.length);
        char[] arr = order.toCharArray();

        for (char i = 'a'; i <= 'z'; i++) {
            map.put(arr[i - 'a'], i);
        }

        String[] strArr = new String[words.length];
        for (int i = 0; i < words.length; i++) {
            String item = words[i];
            char[] cArr = item.toCharArray();
            for (int j = 0; j < cArr.length; j++) {
                cArr[j] = map.get(cArr[j]);
            }
            // 可排序的
            strArr[i] = new String(cArr);
            // 相同的呢?
            if (indexMap.containsKey(strArr[i])) {
                indexMap.put(strArr[i], -1);
                continue;
            }
            indexMap.put(strArr[i], i);
        }

        Arrays.sort(strArr);

        for (int i = 0; i < strArr.length; i++) {
            if (indexMap.get(strArr[i]) != i && indexMap.get(strArr[i]) != -1) {
                return false;
            }
        }


        return true;
    }

}
